\section{Computing a balanced solution} \label{s:balanced}

Recall from Section~\ref{s:prel} that for a background election instance $(G = (N \cup C, E), s, k)$ and a fixed committee $A\subseteq C$, a weight vector $w\in \R^E$ is balanced for $A$ if a) it maximizes the sum of member supports, $\sum_{c\in A} supp_w(c)$, over all feasible weight vectors, and b) it minimizes the sum of supports squared, $\sum_{c\in A} (supp_w(c))^2$, over all vectors that observe the previous property. 
In this section we provide algorithms to compute such a vector.

We start by noticing that a balanced weight vector can be computed with numerical methods for quadratic convex programs. 
Let $E_A\subseteq E$ be the restriction of the input edge set $E$ over edges incident to committee $A$, and let $D\in\{0,1\}^{A\times E_A}$ be the vertex-edge incidence matrix for $A$. 
For any weight vector $w\in\R^{E_A}$, the support that $w$ assigns to candidates in $A$ is given by vector $Dw$, so that $supp_w(c)=(Dw)_c$ for each $c\in A$. 
We can now write the problem of finding a balanced weight vector as a convex program:
\begin{align*}
    \text{Minimize} \quad & \|Dw\|^2 \\
    \text{Subject to } \quad & w\in\R^{E_A}, \\
    & \sum_{c\in C_n} w_{nc} \leq s_n \quad \text{for each } n\in N, \text{ and} \\
    & \mathbbm{1}^{\intercal} Dw = \sum_{n\in \cup_{c\in A} N_c} s_n,
\end{align*}
where the first line of constraints corresponds to non-negativity, the second one to feasibility (see inequality~\ref{eq:feasible}), and the last line ensures that the sum of supports is maximized (see property 2 in Lemma~\ref{lem:balanced}), where $\mathbbm{1}\in\mathbb{R}^A$ is the all-ones vector. 



However, there is a more efficient method using techniques for parametric flow, which we sketch now. Hochbaum and Hong~\cite[Section 6]{hochbaum1995strongly} consider a network resource allocation problem which generalizes the problem of finding a balanced weight vector: given a network with a single source, single sink and edge capacities, minimize the sum of squared flows over the edges reaching the sink, over all maximum flows. 
They show that this is equivalent to a parametric flow problem called \emph{lexicographically optimal flow}, studied by Gallo, Gregoriadis and Tarjan~\cite{gallo1989fast}. 
In turn, in this last paper the authors show that, although a parametric flow problem usually requires solving several consecutive max-flow instances, this particular problem can be solved running a single execution of the FIFO preflow-push algorithm by Goldberg and Tarjan~\cite{goldberg1988new}.

Therefore, the complexity of finding a balanced weight vector is bounded by that of Goldberg and Tarjan’s algorithm, which is $O(n^3)$ for a general $n$-vertex network. 
However, Ahuja et al.~\cite{ahuja1994improved} showed how to optimize several popular network flow algorithms for the case of bipartite networks, where one of the partitions is considerably smaller than the other. Assuming the sizes of the bipartition are $n_1$ and $n_2$ with $n_1 \ll n_2$, they implement a two-edge push rule that allows one to "charge" most of the computation weight to the vertices on the small partition, and hence obtain algorithms whose running times depend on $n_1$ rather than $n$. 
In particular, they show how to adapt Goldberg and Tarjan’s algorithm to run in time $O(e\cdot n_1+n_1^3)$, where $e$ is the number of edges. 
For our particular problem, which can be defined on a bipartite graph $(N\cup A, E_A)$ where $|A|\leq k\ll |N|$, we obtain thus an algorithm that runs in time $O(|E_A|\cdot k + k^3)$.